# -*- coding: utf-8 -*-

'''
@author: Luis Fonte n6043
@date: 10/06/2013
@obs: Adapted from code programmed by teacher in class.
'''

import math
from math import sqrt
from random import uniform, sample
from time import clock
import matplotlib.pyplot as plt
from insertionSort import Insertion
from bubble import Bubble
from heapSort import Heapsort
from mergeSort import MergeAlgorithm
from quicksort import Quick



class AlgorithmsTest():
    '''
    Class AlgorithmsTest
    Main class that uses other classes and functions as libraries
    '''

    
    def __init__(self):
        '''
        Class Constructor
        '''
        self.algorithmChosen = ""   # string to show on graphic wich algorithm was called 
        pass


    def createGraphicFromAlgorithm(self, function_number):
        '''
        Creates graphic with execution time of an algorithm from an object of a class
        Classes imported work like libraries
        @param function_number - number that defines wich algorithm is tested. (numbers 1 to 5)
        '''

        if function_number == 1:
            self.algorithmChosen = "Algorithm Tested: Insertion Sort"
            pass
        elif function_number == 2:
            self.algorithmChosen = "Algorithm Tested: Bubble Sort"
            pass
        elif function_number == 3:
            self.algorithmChosen = "Algorithm Tested: Heap Sort"
            pass
        elif function_number == 4:
            self.algorithmChosen = "Algorithm Tested: Merge Sort"
            pass
        elif function_number == 5:
            self.algorithmChosen = "Algorithm Tested: Quick Sort"
            pass 
        
        Z = [1] + range(50, 1000, 50) # creates a list with values between 1 and 1000, 50 to 50
        T = []  #final list of number values​​, the average times of execution and error values
        M = 25  #number of iterations
        for n in Z:
            A = [ uniform(0.0,1.0) for k in xrange(n)] #creates list with number of values equal to n, with values ​​between 0.0 and 1.0
            times = [] # list with the 25 execution times of the algorithm
            for k in range(M): #exectutes the algorithm 25 times to then calculate average value and obtain a trustable value
                
                t1 = clock()
                if function_number == 1:    
                    I = Insertion(A)
                    I.insertionSort()
                    pass
                elif function_number == 2:
                    B = Bubble(A)
                    B.bubblesort()
                    pass
                elif function_number == 3:  #as the parameter passed is equal to one of these, classe object is created and algotirhm function called
                    H = Heapsort(A) #class object
                    H.sort()   #algorithm function
                    pass
                elif function_number == 4:
                    M_A = MergeAlgorithm(A)
                    M_A.merge_sort()
                    pass
                elif function_number == 5:
                    Q = Quick(A)
                    Q.quick()
                    pass
                
                t2 = clock()
                times.append(t2-t1) #add execution time to list times
                
            mean = reduce(lambda x, y: x + y, times) / len(times) #calculates the mean time of all times
            
            var = reduce(lambda x, y: x + (y-mean)**2, [0] + times) / len(times)
            
            stdDev = sqrt(var)  #standard devitation

            error = stdDev / sqrt(len(times))  # standard error
             
            T.append((n, mean, var, error)) # adds to list new values from new algorithm execution
            # n = value of Z, number of elements of list
            pass
        
        X = [n for n, mean, var, error in T] #number of list elements
        Y = [mean for n, mean, var, error in T] #mean time of execution times
        E = [error for n, mean, var, error in T] #all errors from execution times calculated

        err = reduce(lambda x, y: x + y, E) / len(E) #mean time of error times

        if function_number == 4 or 3: #equation for algorithms heapsort and mergesort in worst case (n*log(n)) aproximated to last value
            Z = [(n*math.log(n, 2) / (T[len(T) - 1][0]*math.log(T[len(T) - 1][0], 2)) * T[len(T) - 1][1]) for n, mean, var, error in T] # 0 é n
        else: #equation for the rest of the algoritms (n^2)
            Z = [n**2 * (Y[len(Y) -1] / X[len(X) -1]**2) for n, mean, var, error in T]
            pass

        import matplotlib.pyplot as plt
        #creation of graphic
        colors = ['w', 'g', 'r', 'c', 'm', 'y', 'b'] #list of colors for plots
        plt.grid(True)
        plt.ylabel(u'T(n) - Average execution time in seconds') #yy label
        plt.xlabel(u'n - Number of Elements') #xx label
        plt.plot(X,Z, colors[function_number+1], label="Theoretical Prediction") #plot for theorical equation of the algorithm growth in time
        plt.plot(X,Y, colors[function_number], label="Experimental Result" + "\n" + "Error:" + str(err)) #plot for executed algorithm
        plt.legend()
        plt.title(self.algorithmChosen) # set the graphic title with the algorithm name
        plt.show()
        pass


Obj = AlgorithmsTest()
Obj.createGraphicFromAlgorithm(5)
# 1 - Insertion Sort
# 2 - Bubble Sort
# 3 - Heap Sort
# 4 - Merge Sort
# 5 - Quick Sort
